package algorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 *
 * 说明：不允许修改给定的链表。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T00142 {
    public static void main(String[] args) {
        ListNode head = build(0, 1,2);
        ListNode listNode = new Solution().detectCycle(head);
        System.out.println(listNode == null ? "null" : listNode.val);
    }

    static ListNode build(int index, int... arr) {
        ListNode head = null;
        ListNode tail = null;
        for (int i = arr.length - 1; i >= 0; i --) {
            ListNode n = new ListNode(arr[i]);
            if(head == null)
                tail = n;
            n.next = head;
            head = n;
        }
        ListNode cur = head;
        while(index-- > 0 && cur != null) {
            cur = cur.next;
        }
        if(tail != null)
            tail.next = cur;
        return head;
    }

static class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null)
            return null;
        ListNode p1 = head, p2 = p1;
        for(;;) {
            p1 = p1.next;
            if(p1 == null)
                break;
            p2 = p2.next;
            if(p2 == null)
                break;
            p2 = p2.next;
            if(p2 == null)
                break;
            if(p1 == p2) { // 有环
                p1 = head;
                for(;;) {
                    if(p1 == p2) // 入环点
                        return p1;
                    p1 = p1.next;
                    p2 = p2.next;
                }
            }
        }
        // 无环
        return null;
    }
}

    private static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}